using System;
using System.Text;
using System.Collections.Generic;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0060. 第k个排列")]
    public class No0060_GetPermutation : AbsBaseTestItem
    {
        public override void OnTest()
        {
            Assert.TestExe(GetPermutation, 3, 3, "213");
            Assert.TestExe(GetPermutation, 4, 9, "2314");
        }

        public string GetPermutation(int n, int k)
        {
            int[] factorial = new int[n];
            factorial[0] = 1;
            for (int i = 1; i < n; ++i)
            {
                factorial[i] = factorial[i - 1] * i;
            }

            --k;
            StringBuilder ans = new StringBuilder();
            int[] valid = new int[n + 1];
            Array.Fill(valid, 1);
            for (int i = 1; i <= n; ++i)
            {
                int order = k / factorial[n - i] + 1;
                for (int j = 1; j <= n; ++j)
                {
                    order -= valid[j];
                    if (order == 0)
                    {
                        ans.Append(j);
                        valid[j] = 0;
                        break;
                    }
                }
                k %= factorial[n - i];
            }
            return ans.ToString();
        }
    }
}
